package cl.regalloc.graph;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Map;

import cl.regalloc.util.LabeledListSet;
import cl.regalloc.util.Pair;

@SuppressWarnings("all")
public class InterferenceGraph implements Cloneable {
	private Map<String, Node> graph;

	public InterferenceGraph() {
		this.graph = new HashMap<String, Node>();
	}
	
	private HashMap alias  = new HashMap();
	private HashMap coalescedNodes = new HashMap();
	private LabeledListSet llSet = null;
	private LinkedList ordering = null;
	private boolean removedColours[] = null;
	private boolean isBuilt = false;
	private boolean isKColourable = true;
	private int availableColours[] = null;
	private int highestColour = 0;
	private int numberOfCoalescing = 0;
	private int numberOfMoveInstructions = 0;
	private LinkedList movePairs = new LinkedList();
	private HashSet<Node> spilledNodes = new HashSet<Node>();
	private HashSet nonSimplicialNodes = new HashSet();
	private boolean isChordal = true;

	public ListIterator getSimplicialEliminationOrdering() {
		if(this.isBuilt)
			return this.ordering.listIterator();
		else {
			this.ordering = new LinkedList();
			this.llSet = new LabeledListSet(this);
			while(llSet.size() > 0) {
				Node node = llSet.getNextNode();
				ordering.add(node.getNodeKey());
				llSet.update(node);
			}
			this.isBuilt = true;
			return ordering.listIterator(0);
		}
	}

	public void colourGraph(int numColours) {
		int originalSize = graph.size();
		this.applyGreedyColouring(100);
		this.spillColour(numColours);
		this.coalesceRegisters();
	}

	public Map<String, Node> getGraph() {
		return this.graph;
	}

	private void disconnectNode(Node n) {
		HashMap<String, Node> succs = n.getSuccs();
		for (Node currentNode : succs.values()) {
			currentNode.removeFromSuccs(n);
		}
	}

	public Node getNewNode(String nodeKey) {
		if (this.graph.containsKey(nodeKey)) {
			return this.graph.get(nodeKey);
		} else {
			System.out.printf("New Node %s created...%n", nodeKey);
			Node newNode = new Node(nodeKey);
			this.graph.put(nodeKey, newNode);
			return newNode;
		}
	}

	public boolean addEdge(Node node1, Node node2) {
		if(!node1.equals(node2)) {
			System.out.printf("New edge added between \"%s\" and \"%s\"!%n", node1.toString(), node2.toString());
			node1.addToSuccs(node2);
			node2.addToSuccs(node1);
			return true;
		}
		return false;
	}
	
	public void applyGreedyColouring(int numColours) {
		Node.setNumColours(numColours);
		this.availableColours = new int[numColours];
		ListIterator li = this.getSimplicialEliminationOrdering();
		while(li.hasNext()) {
			String nodeKey = (String)li.next();
			Node node = graph.get(nodeKey);
			if(!this.isSimplicial(node)) {
				// node is not simplicial
				this.nonSimplicialNodes.add(node);
				this.isChordal = false;
			}
			int aux = 0;
			aux = node.assignColour();
			if (aux < 0) {
				this.disconnectNode(node);
				this.spilledNodes.add(node);
			}
			if (aux > this.highestColour)
				this.highestColour = aux;
		}
	}

	public boolean isSimplicial(Node node) {
		ArrayList<Node> rep = new ArrayList(node.getTotalDegree());
		node.setMcsStatus(Node.MCS_VISITED);        
		for (Node currentNode : node.getSuccs().values()) {
			if(currentNode.getMcsStatus() == Node.MCS_VISITED)
				rep.add(currentNode);
		}
		for(int i = 0; i < rep.size(); i++)
			for(int j = 0; j < rep.size(); j++) {
				Node nodeI = rep.get(i);
				Node nodeJ = rep.get(j);
				if( (nodeI != nodeJ) && !nodeI.succsContains(nodeJ.getNodeKey()))
					return false;
			}
		return true;
	}

	public void spillColour(int numAvailableColours) {
		this.removedColours = new boolean[1000];
		if(this.highestColour < numAvailableColours)
			this.isKColourable = true;
		else {
			int colours[] = this.orderColours(this.highestColour + 1);
			this.removeColours(colours, numAvailableColours);
			this.highestColour = numAvailableColours - 1;
			this.isKColourable = false;
			// remove spilled nodes.
			for(Node currentNode : graph.values()) {
				if(this.isLeastUsedColours(currentNode.getColour(), colours, numAvailableColours)) {
					currentNode.setColour(Node.UNCOLOURED);
					this.disconnectNode(currentNode);
					this.spilledNodes.add(currentNode);
				}
			}
		}
		// rebuild interference graph
		reconnectNodes();
	}

	private int[] orderColours(int hc) {
		int colours[] = new int[hc];
		int result[] = new int[hc];
		for(int i = 0; i < colours.length; i++) {
			colours[i] = 0;
			result[i] = i;
		}
		for (Node currentNode : graph.values())
			colours[currentNode.getColour()]++;

		for(int i = 0; i < colours.length - 1; i++) {
			for(int j = i+1; j < colours.length; j++)
				if(colours[i] > colours[j]) {
					int aux = colours[i];
					colours[i] = colours[j];
					colours[j] = aux;
					aux = result[i];
					result[i] = result[j];
					result[j] = aux;
				}
		}
		return result;
	}

	private void removeColours(int[] colours, int numAvailableColours) {
		for(int i = 0; i < this.removedColours.length; i++)
			this.removedColours[i] = false;
		for(int i = 0; i < (colours.length - numAvailableColours); i++)
			this.removedColours[colours[i]] = true;
	}

	private boolean isLeastUsedColours(int colour, int[] colours, int numAvailableColours) {
		for(int i = 0; i < (colours.length - numAvailableColours); i++)
			if(colour == colours[i])
				return true;
		return false;
	}

	private void reconnectNodes() {
		Iterator i = this.spilledNodes.iterator();
		for (Node currentSpilledNode : this.spilledNodes) {
			Node n = (Node)i.next();
			for (Node currentNode : n.getSuccs().values()) {
				if(this.spilledNodes.contains(currentNode))
					currentNode.addToSuccs(n);
				else
					n.removeFromSuccs(currentNode);
			}
			this.removeMovePairs(n);
			this.removeNode(n);
		}
	}

	private void removeMovePairs(Node n) {
		Iterator i = this.movePairs.iterator();
		while(i.hasNext()) {
			Pair p = (Pair)i.next();
			if(p.getA().equals(n))
				i.remove();
			else if(p.getB().equals(n))
				i.remove();
		}
	}

	private void updateMovePairs(String newKey, String oldKey) {
		for(int i = 0; i < this.movePairs.size(); i++) {
			Pair p = (Pair)movePairs.get(i);
			if(p.getA().equals(oldKey))
				p.setA(newKey);
			else if(p.getA().equals(oldKey))
				p.setB(newKey);
		}
	}
	
	private void removeNode(Node n) {
		if(n != null) {
			for (Node currentSuccNode : n.getSuccs().values())
				currentSuccNode.removeFromSuccs(n);
			for (Node currentPrdcNode : n.getPrdcs().values())
				currentPrdcNode.removeFromPrdcs(n);
		}
	}

	public void coalesceRegisters() {
		this.numberOfMoveInstructions = this.movePairs.size();
		while(movePairs.size() > 0) {
			Pair mp = (Pair)movePairs.removeFirst();
			this.coalescePair(mp);
		}
		this.colourCoalescedRegisters();
	}

	private void coalescePair(Pair<Node> mp) {
		for(int i = 0; i < this.availableColours.length; i++)
			this.availableColours[i] = -1;
		Node src = mp.getA();
		Node dst = mp.getB();
		if(this.spilledNodes.contains(src) || this.spilledNodes.contains(dst)) {
			return;
		} else if(src == null || dst == null) {
			return;
		} else if(!src.isAdjacent(dst.getNodeKey())) {
			this.setCoalesceColour(src, dst);
			boolean successfullCoalescing = false;
			for(int i = 0; i < this.availableColours.length; i++)
				// test to see if colour has being removed
				if(this.availableColours[i] < 0 && !this.removedColours[i]) {
					this.combine(src, dst, i);
					successfullCoalescing = true;
					this.numberOfCoalescing++;
					break;
				}
		}
	}

	private void setCoalesceColour(Node src, Node dst) {
		for (Node currentSucc : src.getSuccs().values())
			this.availableColours[currentSucc.getColour()] = 1;
		for (Node currentSucc : dst.getSuccs().values())
			this.availableColours[currentSucc.getColour()] = 1;
	}

	private void combine(Node u, Node v, int newColour) {
		u.copyToSuccs(v);
		u.setColour(newColour);
		this.removeNode(v);
		v.clearSuccs();
		this.coalescedNodes.put(v.getNodeKey(), v);
		this.updateAlias(v, u);
		this.updateMovePairs((String)u.getNodeKey(), v.getNodeKey());
	}

	private void updateAlias(Node v, Node u) {
		this.alias.put(v, u);
		java.util.Set keys = this.alias.keySet();
		Iterator i = keys.iterator();
		while(i.hasNext()) {
			Node cn = (Node)i.next();
			Node actualValue = (Node)alias.get(cn);
			if(actualValue.equals(v)) {
				alias.put(cn, u);
			}
		}
	}

	private void colourCoalescedRegisters() {
		Iterator i = this.alias.keySet().iterator();
		while(i.hasNext()) {
			Node cn = (Node) i.next();
			Node actualValue = (Node) alias.get(cn);
			cn.setColour(actualValue.getColour());
		}
	}

	public void printAdjacencies() {
		System.out.printf("%n%nPrinting adjacencies...%n");
		for (String currentKey : this.graph.keySet()) {
			System.out.printf("\"%s\" - [", currentKey);
			for (String currentAdj : this.graph.get(currentKey).getSuccs().keySet())
				System.out.printf("%s, ", currentAdj);
			System.out.printf("]%n");
		}

	}

	public HashMap<String, Integer> yieldResult() {
		HashMap<String, Integer> rsMap = new HashMap<String, Integer>();

		for (String currentKey : this.graph.keySet()) {
			Node currentNode = this.graph.get(currentKey);
			rsMap.put(currentKey, currentNode.getColour());
		}
		return rsMap;
	}
}
